package bank;

public class _05PalindromeStr {
    public static String longestPalindrome01(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        int maxlen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        //枚举长度>=2的子串：暴力解法！时间复杂度O(n3)
        //也有其他方法如中心扩散法O(n2)
        for(int i = 0;i < len-1;i++){
            for(int j = i+1;j<len;j++){
                if(j-i+1>maxlen && validPalindromic(charArray,i,j)){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxlen);
    }
    private static boolean validPalindromic(char[] charArray, int left, int right) {
        while(left < right){
            if(charArray[left++] != charArray[right--]){
                return false;
            }
        }
        return true;
    }

    //动态规划法O(n2)
    /*
    状态description dp[i][j]表示子串s[i,j]是否为回文子串
    dp[i][j] = (s[i] == s[j]) && (dp[i+1][j-1] || j-i<3)
    注意边界条件：(j-1)-(i+1)+1 < 2的时候，即：j-i < 3时，子串的长度为2或3，此时不用检查
    这样做的好处是：每一次计算都用到了之前计算的结果！思想是：空间换时间！
    */
    public static String longestPalindrome02(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        int maxlen = 1;
        int begin = 0;

        //dp为二维数组，实际上是一个倒三角的二维数组，因为i<=j
        boolean[][] dp =new boolean[len][len];
        for(int i = 0;i < len;i++){
            //对角线上的元素
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();

        //填写状态表，左下角先填
        for (int j = 0;j < len ;j++){
            for (int i = j-1;i >= 0;i--){
                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;
                }else {
                    if(j-i <3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1 > maxlen){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxlen);
    }

    //最优解法：Manacher算法O(n)马拉车算法
    public static String longestPalindrome03(String s) {
        return null;
        //太难了，放过我吧！
        /*
        https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
        */
    }
}
